#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include "allocator_interface.h"
#include "memlib.h"
#include "allocator_util.h"

/* All blocks must have a specified minimum alignment. */
#define ALIGNMENT 8

/* Rounds up to the nearest multiple of ALIGNMENT. */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1))

/* The smallest aligned size that will hold a size_t value. */
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

//find out what's the max value here?
#define N_BINS 32

/* We use a reguler bin approach
 * bins have exponential sizes, 2^5, 2^6, ..., 2^32
 * we do some basic coalescing
 */

namespace my
{
  void * allocator::bin_pointers[N_BINS] = {NULL};
  pthread_mutex_t allocator::mutex;

  /*
   * check - This checks our invariant that the size_t header before every
   * block points to either the beginning of the next block, or the end of the
   * heap.
   */
  int allocator::check()
  {
    char *p;
    char *lo = (char*)mem_heap_lo();
    char *hi = (char*)mem_heap_hi() + 1;
    size_t size = 0;

    p = lo;
    while (lo <= p && p < hi) {
      size = ALIGN(*(size_t*)p + SIZE_T_SIZE);
      p += size;
    }

    if (p != hi) {
      printf("Bad headers did not end at heap_hi!\n");
      printf("heap_lo: %p, heap_hi: %p, size: %lu, p: %p\n", lo, hi, size, p);
      return -1;
    }

    return 0;
  }

  /*
   * init - Initialize the malloc package.  Called once before any other
   * calls are made.  Since this is a very simple implementation, we just
   * return success.
   */
  int allocator::init()
  {
    for (int i = 0; i < N_BINS; i++)
      bin_pointers[i] = NULL;
    pthread_mutex_unlock(&mutex);
    return 0;
  }

  /*
   * malloc - Allocate a block by incrementing the brk pointer.
   *     Always allocate a block whose size is a multiple of the alignment.
   */
  void * allocator::malloc(size_t size)
  {
    if (size == 0)
      return NULL;

    /* We allocate a little bit of extra memory so that we can store the
       size of the block we've allocated.  Take a look at realloc to see
       one example of a place where this can come in handy. */
    int aligned_size = ALIGN(size + SIZE_T_SIZE);
    
    int val = getBinIndex(size + SIZE_T_SIZE) - 4;

    if (val < 0) //Set to zero if it's too small since we start at 2^5
      {
	val = 0;
      }

    pthread_mutex_lock(&mutex);
    if (val >= 31) //If we need 2^35 bytes or more.
      {
	void *p = mem_sbrk(aligned_size); //Then we just grab it directly
	if (p == (void *)-1) 
	  {
	    pthread_mutex_unlock(&mutex);
	    return NULL; //(we perhaps should do this elsewhere)
	  }
	*(size_t*)p = aligned_size-SIZE_T_SIZE;
	pthread_mutex_unlock(&mutex);
	return (void *)((char *)p + SIZE_T_SIZE);
      } 
    else //look thru the bins 
      {
	int index = findEmptyBin(val);
	//printf("got index %d\n", index);
	if (index == N_BINS) //no empty bin, need to expand the heap
	  {
	    pthread_mutex_unlock(&mutex);
	    return expandHeap(val);
	  }
	
	if (index == val) //no splitting ?! - we need to split here too!
	  {
	    void *p = bin_pointers[val];
	    remove_from_bin(p, val);
	    //extractChunk(p, size, val);
	    pthread_mutex_unlock(&mutex);
	    return (void *)((char *)p + SIZE_T_SIZE);
	  } 
	else 
	  {
	    void *p_chunk = bin_pointers[index];
	    remove_from_bin(p_chunk, index);
	    void *p = split(p_chunk, 1<<(index + 4), 1<<(val+4));
	    pthread_mutex_unlock(&mutex);
	    return p;
	  }
      }
    pthread_mutex_unlock(&mutex);
  }

  /*void *allocator::extractChunk(void *p, size_t req_size, int val)
  {
    void *q = ALIGN(SIZE_T_SIZE + req_size);
    }*/

  void * allocator::split(void * p, size_t size, size_t size_needed){
    size_t new_size = size/2;
    setBlockSize((char *)p + new_size, new_size); //set size of second half
    int x = getBinIndex(new_size) - 4;
    add_to_bin((void *)((char *)p+new_size), x);//put second half in bin
    if (new_size == size_needed){
      setBlockSize(p, size_needed); //set size of first half
      return (void *)((char *)p+SIZE_T_SIZE); //return first half
    }
    else{
      return split(p, new_size, size_needed);//recurse on first half
    }
  }

  void allocator::add_to_bin(void * ptr, int bin_index) {
    void *p = insertToList(&bin_pointers[bin_index], ptr);
    if (p) //coalesce
      {
	//printf("coalesce!");
	add_to_bin(p, bin_index+1);
      }
  }

  void allocator::remove_from_bin(void * ptr, int bin_index){
    removeFromHead(&bin_pointers[bin_index], ptr);
  }

  /*
   * free - Freeing a block does nothing.
   */
  void allocator::free(void *ptr)
  {
    pthread_mutex_lock(&mutex);
    if (ptr != NULL){
      void * b_ptr = (void *)((char*) ptr -8); //move to beginning of block
      size_t size = *((size_t*)b_ptr); //read size
      if (size <= (1LL<<35)) {
	int bin_index = getBinIndex(size) - 4;
	add_to_bin(b_ptr, bin_index); //add freed block to appropriate bin
      }
    }
    pthread_mutex_unlock(&mutex);
  }

  /*
   * realloc - Implemented simply in terms of malloc and free
   */
  void * allocator::realloc(void *ptr, size_t size)
  {
    void *newptr;
    size_t copy_size;

    /* Allocate a new chunk of memory, and fail if that allocation fails. */
    newptr = malloc(size);
    if (NULL == newptr)
      return NULL;

    /* Get the size of the old block of memory.  Take a peek at malloc(),
       where we stashed this in the SIZE_T_SIZE bytes directly before the
       address we returned.  Now we can back up by that many bytes and read
       the size. */
    copy_size = *(size_t*)((uint8_t*)ptr - SIZE_T_SIZE);

    /* If the new block is smaller than the old one, we have to stop copying
       early so that we don't write off the end of the new block of memory. */
    if (size < copy_size)
      copy_size = size;

    /* This is a standard library call that performs a simple memory copy. */
    std::memcpy(newptr, ptr, copy_size);

    /* Release the old block. */
    free(ptr);

    /* Return a pointer to the new block. */
    return newptr;
  }

  /* call mem_reset_brk. */
  void allocator::reset_brk()
  {
    for (int i = 0; i < N_BINS; i++)
      bin_pointers[i] = NULL;
    mem_reset_brk() ;
  }

  /* call mem_heap_lo */
  void * allocator::heap_lo()
  {
    return mem_heap_lo() ;
  }

  /* call mem_heap_hi */
  void * allocator::heap_hi()
  {
    return mem_heap_hi() ;
  }

  int allocator::findEmptyBin(int start_index)
  {
    while (start_index < N_BINS && bin_pointers[start_index] == NULL)
      start_index++;
    return start_index;
  }

  void *allocator::expandHeap(int val)
  {
    if (val < 10)
      {
	void * p_block = mem_sbrk(32768); //So we expand the heap
	void * p = split(p_block, 32768, 1<<(val+4)); //And split up
	return p;
      } 
    else 
      {
	void * p_block = mem_sbrk(1<<(val+4+1));
	void * p = split(p_block, 1<<(val + 4 + 1), 1<<(val+4));
	return p;
      }      
  }
};
